package com.mlh.binarytree;

import java.util.HashMap;
import java.util.HashSet;

public class LowestCommonAncestor {
	//解法一
	public static TreeNode lowestAncestor(TreeNode head,TreeNode o1,TreeNode o2){
		//找到o1或o2节点 或者该节点为null此次递归停止，返回
		if(head==null||head.val==o1.val||head.val==o2.val){
			return head;
		}
		//在自己的右树找  左树找
		TreeNode left=lowestAncestor(head.left,o1,o2);
		TreeNode right=lowestAncestor(head.right,o1,o2);
		//left和right同时不为空，只可能在最低公共祖先节点发生，因此返回该节点
		if(left!=null&&right!=null){
			return head;
		}
		//这边处理了两种情况
		//第一就是将已经找到的最低公共节点抛上去
		//第二就是子树找到了o1 和 o2 的某个 但是另外一个没找到
		//第三就是最低公共点是o1 或者 o2本身
		//这三种情况下 left 和right 必定有一个是null
		//这里不太好解释，去看代码随想录
		return left!=null?left:right;
	}
}

// 解法二
class LowestCommonAncestor2 {
	//利用map 和 set
	private HashMap<TreeNode, TreeNode> map;
	//先将根节点存入map中
	public void record(TreeNode head) {
		map = new HashMap<TreeNode, TreeNode>();
		if (head != null) {
			map.put(head, null);
		}
		setMap(head);
	}

	//map中存储了每个节点的父节点
	private void setMap(TreeNode head) {
		if (head == null) {
			return;
		}
		if (head.left != null) {
			map.put(head.left, head);
		}
		if (head.right != null) {
			map.put(head.right, head);
		}
		setMap(head.left);
		setMap(head.right);
	}
	//开始寻找最低公共节点
	public TreeNode query(TreeNode o1, TreeNode o2) {
		HashSet<TreeNode> path = new HashSet<TreeNode>();
		while (map.containsKey(o1)) {
			path.add(o1);
			o1 = map.get(o1);
		}
		//如果包含的话 说明o2是o1的父节点 此时最低共同祖先就是o2
		//如果set不包含o2  就去找o2的祖先节点 直到有和o1有共同祖先为止
		while (!path.contains(o2)) {
			o2 = map.get(o2);
		}
		return o2;
	}
}